系白书上的一道队列题，初来乍到谈一下我对这个最短路SPFA的算法的理解  首先队列是先进先出，即push元素增加队列尾部，pop移除队列头部的元素  这个算法注意要标记之前走过的位置，然后开一个二维数组封装一下每个位置到起始点的最短距离  在这些前提之下至于为什么这样是最短的，比如如果产生分岔的路，这多条分岔的路基本是同时行进的，  如果走到了同一个位置，先到的那条路已经把这个点走过了，做好了标记，其他的路就无法再走了，所以最短。  源代码：

que; char maps[maxn][maxn]; int sx,sy,ex,ey,n,m; int d[maxn][maxn]; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,1,-1}; int bfs(int x,int y) { d[x][y] = 0; que.push(P(x,y)); while(que.size()) { P a = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int nx = a.first + dx[i]; int ny = a.second + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] != '#' && d[nx][ny] == INF)//只有没走过的才可以 { que.push(P(nx,ny)); d[nx][ny] = d[a.first][a.second] + 1; } } } return d[ex][ey];//改变此处的坐标可以求出任意可以走到的点到起始点的最短距离 } int main() { freopen("input.txt","r",stdin); scanf("%d%d",&n,&m); getchar(); for(int i = 0; i < n; i++) scanf("%s",maps[i]); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(maps[i][j] == 'S') { sx = i; sy = j; } if(maps[i][j] == 'G') { ex = i; ey = j; } d[i][j] = INF; } printf("%d\n",bfs(sx,sy)); return 0; }